#include <algorithm>
#include <cstdint>
#include <iostream>
#include <istream>
using ll = int64_t;

const ll maxn = (1 << 16) + 5, inf = 1e9 + 7;
ll W, n;
ll max[maxn], w[maxn], dp[maxn];

int main() {
    std::iostream::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin >> W >> n;
    for (ll i = 0; i < n; i++) {
        std::cin >> max[1 << i] >> w[1 << i];
    }
    for (ll i = 3; i < (1 << n); i++) {
        const ll lb = i & -i;
        max[i] = std::max(max[lb], max[i ^ lb]);
        w[i] = w[lb] + w[i ^ lb];
    }
    std::fill(dp, dp + (1 << n), inf);
    dp[0] = 0;
    for (ll S = 1; S < (1 << n); ++S) {
        for (ll P = S; P; P = (P - 1) & S) {
            if (w[P] <= W) {
                ll pS = S ^ P;
                if (dp[pS] != inf) {
                    dp[S] = std::min(dp[S], dp[pS] + max[P]);
                }
            }
        }
    }

    std::cout << dp[(1 << n) - 1] << "\n";
}